\documentclass[UTF8]{book}
\usepackage{titletoc}
\usepackage[noindent]{ctex}
\usepackage{indentfirst}
\usepackage{listings}
\usepackage[colorlinks,linkcolor=red]{hyperref}
\hypersetup{colorlinks=true,linkcolor=black}
\usepackage{geometry}

\usepackage{graphicx}
\graphicspath{{images/}}

\usepackage{caption}

\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric}
\usepackage{array}

\geometry{left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm}

\begin{document}

\tableofcontents

\chapter{Latex学习笔记}
    \section{基本知识}
    \section{Tikz学习}
        \subsection{基本用法}
            %https://en.wikibooks.org/wiki/LaTeX/PGF/TikZ#Nodes
		\url{https://en.wikibooks.org/wiki/LaTeX/PGF/TikZ#Nodes}


\chapter{C++ 学习笔记}
    \section{常识}
        extension file name不一定是.h或.cpp也可能是.hpp或其他或甚至无延伸名。

        c++中的二元操作符都是作用在操作符右侧的变量上。

        cout是一个global对象，它的type为ostream。
    \section{基础学习}
        \subsection{Header的布局}
            结合实例：
            \begin{lstlisting}[language=C++]
            //guard
            #ifndef __XXX__
            #define __XXX__

            #include <cmath>

             //forward declarations
            class ostream;
            class complex;
            complex & __doapl (complex* ths,const complex& r);

            //class declarations
            class complex      //class head
            {
           //class body,简短的函数可以在这里直接定义即inline。
            //function。最后是否为inline由编译器决定，
            //若在body外定义inline function //可以通过添加关键字inline
            };

            //class definition
            complex::function ...

            #endif
            \end{lstlisting}
        \subsection{UML符号}
        +:public，-:private，$\#$:protect,下划线静态。
        \subsection{function template}
        \begin{lstlisting}[language = C++]
            template <class T>
            inline
            const T& min(const T& a,const T& b)
            {
                return b<a ? b:a;//<会使用重载后的小于函数。
            }

        //使用
        stone r1(2,3),r2(3,3),r3;
        r3 = min(r1,r2);
        //编译器会对functoin template进行形参推导(argument deduction)
        //即根据参数的类型来选定模板函数中T的值。
        \end{lstlisting}
        \subsection{class template介绍}
        \begin{lstlisting}[language = C++]
            template<typename T>//告知编译器数据类型未定
            class complex
            {
            public://access level
                //constructor，ctor构造函数
                complex(T r=0,T i=0)//默认实参default argument
                    :re(r),im(i)//初值列initialization list构造函数独有比较大气
                {}
                complex& operator += (const complex&);
                T real () const {return re;}
                T imag () const {return im;}
            private:
                T re,im;

                friend complex& __doapl(complex*,const complex&);
            };

            //使用：
            complex<double> c1(2.5,1.5);
            complex<int> c2(2,6);
            ...
            }
        \end{lstlisting}
        \subsection{composition}
        特例：

            Adapter；弱功能结构包含强功能结构。

        符号：实心菱形。

        生命周期：

            Container和Component同生命周期。

        构造由内而外。
        \begin{lstlisting}[language = C++]
        Container::Container():Component(){};//Component由编译器来处理
        \end{lstlisting}
        析构由外而内。
        \begin{lstlisting}[language = C++]
        Container::~Container(){~Component()};
        \end{lstlisting}


        \subsection{Delegation}
        composition by reference(包括指针和引用)。

        符号：空白菱形。

        生命周期：

            主体和被委托对象的生命周期不一致，被委托对象只有在被需要时才被创建。

        如：
        \begin{lstlisting}[language = C++]
        //将Handle和Body分开来。
        //file String.hpp
        class StringRep;
        class String
        {
            ...
        private:
            StringRep * rep;//point to implementation
                            //另一个好处是可以实现body共享copy时的共享
        };
        //file StringRep.hpp//编译防火墙
        class StringRep
        {
            friend class String;
            ...
            int count;//共享copy的个数
                    //若一个copy对象发生copy on write时，
                    //可以单独再这个对象分配body 并write修改内容
        }
        \end{lstlisting}
        \subsection{inheritance和虚函数}
            有private、protect、public三种继承。

            继承最有价值之处在于：和虚函数的搭配使用with virtual fucntions。

            注意：base class 的dtor必须是virtual，否则会出现undefined behavior。

        符号：空心三角形。

        构造由内而外。

        析构由外而内。
        \subsection{DIC组合}
        最常用的组合：Delegation和Inheritance。

        1、观察者模式：处理存储数据和表现数据之间的关系。

        2、Composite。

        3、Prototype。
        \subsubsection{virtual functions}
        分两类：1、pure virtual，2、impure virtual。

        impure virtual已有默认定义。

        实例：
        \begin{lstlisting}[language = C++]
        class Shape
        {
            public:
                virtual void draw()const=0;//纯虚函数后添加了=0
                virtual void error(const std::string& msg){};//impure virtual
            ...
        }
        \end{lstlisting}
        \subsection{构造函数}
            \subsubsection{构造函数可以overloading重载}
            如：
                \begin{lstlisting}[language = C++]
                complex(double r=0,doublei=0)
                    :re(r),im(i)
                { }
                complex():re(0),im(0){ }
                \end{lstlisting}
            \subsubsection{构造函数放在private中}
            如singleton单体
                \begin{lstlisting}[language = C++]
                class A
                {
                    public:
                        static A& getInstance();//静态
                        setup(){...}
                    private:
                        A();
                        A(const A& rhs);
                        ...
                };
                A& A::getInstance()
                {
                    static A a;//这个设计只给静态创建一份
                    return a;
                }
                }
                \end{lstlisting}

        \subsection{对<<的重载}
            \begin{lstlisting}[language = C++]
            ostream&
            operator << (ostream& os,const type& )
            {
                return os << '(';
                ...
            }
            \end{lstlisting}
        \subsection{常量成员函数}
            如：不会改变数据内容
            \begin{lstlisting}[language = C++]
            class complex
            {
            ...
                double real()const {return re;}
            ...
            }
            \end{lstlisting}
            常会出现的逻辑矛盾
            \begin{lstlisting}[language = C++]
            class complex
            {
                ...
                double real(){return re;}//设计者定义re可变
                ...
            }
            //使用者
            {
                const complex c1(2,1);//使用者定义使用的复数不可变
                cout << c1.real();
            }
            \end{lstlisting}
        \subsection{参数传递和返回值传递}
            \subsubsection{pass(return) by value vs.pass(return) by reference引用(to const)}
            pass（return） by value:它是整包传递并压入stack中。所以尽量不要使用。

            解决：

                1、过去使用指针，只传递指针。

                2、在c++中使用引用（pass（return） by refernce）。

            指针和引用的区别：

            本质上是一样的都是指针，引用是c++对指针做了一个外包装（对地址封装），使

            用更方便。

            引用的使用应该避开local object。

            pass（return） by reference（to const）:

                引用和不可改。
            \subsubsection{创建临时对象temp object}
                使用typename()来创建临时对象，没有变量名，它的生命在下一行结束。
        \subsection{friend友元}
            在c++中，朋友之间可以直接取数据，打破封装自由取得friend的private成员。
            \subsubsection{相同class的各个objects互为friends友元}
            如：
            \begin{lstlisting}[language = C++]
                class complex
                {
                    public:
                        complex (double r=0,double i=0)
                        :re(r),im(i)
                        {
                        }
                        int func(const complex& param)
                        { return param.re + param.im;}
                    private:
                        double re,im;
                };

                {
                    complex c1(2,1);
                    complex c2;

                    c2.func(c1);
                }
            \end{lstlisting}
        \subsection{class中的static}
            静态函数中不能使用this指针，即静态函数中只能处理静态变量。

            静态变量必须在class声明后定义。
            如：
            \begin{lstlisting}[language = C++]
            class Account
            {
            public:
                static double m_rate;
                static void set_rate(const double &x){m_rate = x;}
            };
            double Account::m_rate = 8.0;
            \end{lstlisting}
            调用static函数的方法：

            1、通过object调用。

            2、通过class name调用。
        \subsection{template template parameter}
        \begin{lstlisting}[language = C++]
        template<typename T,
            template<typename T>
                class Container   //class和typename在<>中意义相同
                >
        class XCls
        {
            private:
                Container<T> c;
            public:
                ...
        };
        template<typename T>
        using Lst = list<T,allocator<T>>;

        XCls<string,list> mylst1;//错误，因为list容器有第二模板参数
        XCls<string,Lst> mylst2;
        \end{lstlisting}
        \begin{lstlisting}[language = C++]
        //以下为不是template template parameter的典型
        template <class T,class Sequence = deque<T>>
        class stack
        {
            ...
        }
        stack<int> s1;
        stack<int,list<int>> s2;
        \end{lstlisting}
        \subsection{variadic数量不定template}
        \begin{lstlisting}[language = C++]
        void print()
        {
        }
        template<typename T,typename... Types>
        void print(const T&firstArg,const Types&... args)
        {
            cout<<firstArg<<endl;
            print(args...);
        }
        //bit模板的使用:bitset<16>(377);
        \end{lstlisting}
        \subsection{auto}
        \begin{lstlisting}[language = C++]
        //版本一
        list<string> c;
        ...
        list<string>::iterator ite;
        ite = find(c.begin(),c.end(),target);
        //版本二
        list<string> c;
        ...
        auto ite = find(c.begin(),c.end(),target);
        //错误版本
        list<string> c;
        ...
        auto ite;
        ite = find(c.begin(),c.end(),target);
        \end{lstlisting}
        \subsection{ranged-base for pass by value or reference}
        \begin{lstlisting}[language = C++]
        vetor<double> vec;
        ...
        for(auto elem:vec)
        {
            cout<<elem<<endl;//pass by value
        }

        for(auto& elem:vec)
        {
            elem *=3;//pass by reference
        }
        \end{lstlisting}
        \subsection{reference}
        引用：reference to 对象，指针：pointer to 对象。

        常用于参数传递，而不常用于声明变量。
        \begin{lstlisting}[language = C++]
        int x=0;
        int *p = &x;
        int & r=x;//r代表x。现在r,x都是0，r只是一个假象
        int x2=5;

        r=x2;//r 不能重新代表其他物体。现在r,x都是5
        int & r2=r;

        //注意：same signature
        double imag(const double & im){ ...}
        double imag(const double im){ ...}

        //注意：different signature
        double imag(const double & im)const{...}
        double imag(const double & im){...}
        \end{lstlisting}
    \section{内存管理}
        \subsection{基本构件}
            \subsubsection{new and delete}
                new主要做了两个事：1、分配内存memory，2、调用构造函数ctor。

                delete主要做了：1、析构函数dtor，2、释放内存memory。
        \subsection{动态分配内存块}
            \subsubsection{new and delete}
            gnu编译器下memory block的字节数为16的倍数，memory block在release mode下的组成为：有用块+cookie（8个字节）。

            cookie:something about bookeeping，主要是记录内存块的长度。

            小饼干是malloc和free之间的约定。

            在调试模式下的memory block占用的内存会大的多，每个内存块都需要大约50 个字节的附加信息。
            \subsubsection{new array}
            当array中元素为指针时，array new 和array []delete需要搭配使用，否则会导致memory leak。当array中元素不为指针时，array new和array []delete不搭配使用可能会造成内存泄漏，视array中object的析构函数是否有意义而定。

            array new会多次调用默认构造函数，即使用array new时必须要有默认构造函数。
            形如：
            \begin{lstlisting}[language = C++]
                A* buf=new A[size];
                delete []buf;
            \end{lstlisting}
            改进：
            \begin{lstlisting}[language = C++]
            A* buf = new A[size]//分配空间并调用默认构造函数
            A* tmp =buf;
            for(int i=0;i<size;++i)
                new(tmp++)A(i);//调用构造函数。
            delete []buf;
            \end{lstlisting}
            \subsubsection{placement new}
            没有placement delete，placement new 允许将object建立与allocated memory 中，placement new 根本没分配memory。
            形如：
            \begin{lstlisting}[language = C++]
            #include <new>
            char * buf=new char[sizeof(Complex)*3];
            Complex * pc=new(buf)Complex(1,2);
            ...
            delete [] buf;
            \end{lstlisting}
        \subsection{allocator的选择}
        gnuc++体制内自带标准的allocator对内存没有进行管理，建议使用外带$\_\_pool\_alloc$。
        \subsection{free-list}
        注意内存管理的阶段：1、自由内存，2、被free-list管理的内存（需要embeded pointers），3、被客户管理的内存（使用客户容器对象来取代embeded pointers）
        \subsection{new handler处理内存分配不足的异常}

        \subsection{default and delete}
            拷贝构造、拷贝复制、析构会有默认函数。
            \begin{lstlisting}[language = C++]
            //如：
            class xxx{
                void function()=default;
            }
            \end{lstlisting}
        \subsection{Ctor和Dtor直接调用}
            Ctor不能被直接调用，Dtor可以被直接调用。
    \section{算法}
        \subsection{动态规划和递归}
        DP：dynamic planning。

        相同点：能分解成若干子问题。

        不同点：DP储存子问题的结果。

        1、bottom-up

        2、top-down
        fibonacci number
        \begin{lstlisting}[language = C++]
            int array[n] = {0};
            array[1] = 1;
            for(int i=2;i<n;i++)
                array[i]=array[i-1]+array[i-2];//空间换时间。
        \end{lstlisting}

    \section{Object Based面对的是单一class的设计}
        \subsection{class without pointer members}
            多半不用写析构函数。
        \subsection{class with pointer members}
            带指针需要写析构函数。
        class with pointer members必须有copy ctor和copy op=

        在拷贝复制函数中应该注意“self assignment”

        \begin{lstlisting}[language = C++]
        if(this == &object)
            return *this;
        \end{lstlisting}
    \section{高阶}
        \subsection{conversion function}
        1、转换出去（只要合理，转换函数不唯一）
        \begin{lstlisting}[language = C++]
            class Fraction
            {
                public:
                    Fraction(int num,int den=1)
                    :m_numerator(num),m_denominator(den)
                    { }
                    operator double()const
                    {//转换函数，以返回类型为函数名
                        return (double)(m_numerator/m_denominator);
                    }
                    Fraction operator+(const Fraction& f)
                    {
                    }
                private:
                    int m_numerator;
                    int m_denominator;
            }
        //使用
        Fraction f(3,5);
        double d=4+f;//调用operator double 将f转换为double类型

        Fraction d2 = f+4//error它产生了二义性，第一条：0.6+4=4.6
                        //第二条：3/5+4=23/4
        \end{lstlisting}

        \subsection{non-explicit-one-argument ctor}
        2、转进来。

        可以将别的东西4转为想要的东西4/1。
        \begin{lstlisting}[language = C++]
        class Fraction
        {
        public:
            Fraction(int num,int den=1)//one-argument,只要一个实参,另个形参有默认值
            :m_numerator(num),m_denominator(den){ }
            Fraction operator+(const Fraction& f)
            {
            }
        private:
            int m_numerator;
            int m_denominator;
        };

        Fraction f(3,5);
        Fraction d2=f+4;//调用 non-explicit ctor 将4转为Fraction(4,1)
                        //然后调用operator+

        \end{lstlisting}
        \subsection{explicit-one-argument ctor}
        明确的，不会自动将4转化为分数类型。
        \begin{lstlisting}[language = C++]
        class Fraction
        {
        public:
            explict Fraction(int num,int den=1)//one-argument,只要一个实参,另个形参有默认值
            :m_numerator(num),m_denominator(den){ }
            Fraction operator+(const Fraction& f)
            {
            }
        private:
            int m_numerator;
            int m_denominator;
        };

        Fraction f(3,5);
        Fraction d2=f+4;//error因为4不会被转换为分数，所以在调用operator+
                        //会出现实参形参类型不一致的错误。
        \end{lstlisting}
        \subsection{pointer-like classes智能指针}
        比指针多一些功能，如对++和--进行重载。实例：迭代器。

        \subsection{function-like classes 仿函数或函数对象}
        funciton( )为function call operation。

        标准库中有很多仿函数。

        如：
        \begin{lstlisting}[language = C++]
        template <class T>
        struct identity：unary_function //identity意为视为同一
        {
            const T&
            operator()(const T& x)const{return x;}
        };
        template <class Pair>
        struct select1st: unary_function
        {
            const typename Pair::first_type&
            operator()(const Pair&x)const
            {return x.first}
        };
        \end{lstlisting}
    \section{GOF设计模式}
        模式：可复用面向对象的软件。

        底层思维：向下，如何把握底层从微观理解对象构造。（语言构造、编译转换、内存模型、运行时机制）

        封装，隐藏内部实现。

        继承，复用现有代码。

        多态，改写对象代码，各负其责。

        抽象思维：向上，如何将我们的自卫世界抽象为程序代码（面向对象、组件封装、设计模式、架构模式）

        依赖关系：编译时依赖。

        如何解决复杂性？

        1、分解，各种类型分而治之不易复用。2、抽象，忽视非本质细节并使用通用的方法统一处理。
        \subsection{面向对象设计原则}
            面向对象的最大优势在于：抵御变化，提高复用。

            扩展=继承+override多态。

            变化：各类指针、继承后override虚函数（扩展）、引用（不常用）。

            稳定：函数、变量。
            \subsubsection{对象是什么？}
            1、语言层面：封装了代码和数据。

            2、规格层面：一系列可被使用的公共接口。

            3、概念层面：拥有责任的抽象。
            \subsubsection{重构获得模式}
            1.什么是好的面向对象设计？

                能应对变化，提高复用。
            2.软件设计的特征：需求的频繁变化。

              设计模式的要点是寻找变化点，然后在变化点处应用设计模式，从而来更好地应对需求的变化。（什么时候、什么地点应用设计模式？）

            3.没有一步到位的设计模式，Refactoring to Patterns。（重构完善）

            《重构与模式》和《重构-改善既有代码的设计》

            \subsubsection{DIP依赖倒置原则:稳定隔离变化}
            概述:

            高层模块（稳定）不应该依赖于底层模块（变化），二者度应该依赖于抽象（稳定）。

            抽象（稳定）不应该依赖于实现细节（细节），实现细节应该依赖于抽象（稳定）。

            \begin{tikzpicture} [
               auto,
               block/.style    = { rectangle, draw=blue, thick,
                        fill=blue!20, text width=10em, text centered,
                        rounded corners, minimum height=2em },
               block_noborder/.style ={rectangle, draw=none, thick, fill=none,
                      text width=10em, text centered, minimum height=1em},
               line/.style     = { draw, thick, ->, shorten >=2pt }
            ]
            \matrix [column sep=10mm, row sep=3mm] {
                \node [block] (b1) {Mainform:稳定、高层模块};
                & \node [block] (b2) {Rect:变化、底层模块};
                \\ \node [block_noborder] (b) {Bad!};
                &\node [block] (b5) {Line:变化、底层模块};&
                \\\\ 			
                \node [block] (b3) {Shape:稳定、抽象};
                &\node [block] (b4) {Rect:变化、底层模块};\\
                \node [block_noborder] (b) {Bad!};
                &\node [block] (b6) {Line:变化、底层模块};
                \\\\
                \node [block] (b8) {Shape:稳定、抽象};
                &\node [block] (b9) {Rect:变化、底层模块}; \\
                \node [block_noborder] (b) {依赖倒置原则};
                &\node [block] (b0) {Line:变化、底层模块}; \\

                &\node [block] (b7) {Mainform:稳定、高层模块};\\
            };

            \begin{scope} [every path/.style={line}]
	           \path(b1) -- (b2);
	           \path(b1) --++ (2,0) node [near start]{} |-(b5);
	           \path(b3) -- (b4);
	           \path(b3) --++ (2,0) node [near start]{} |-(b6);
	           \path(b7) --++ (-2,0)node [near start]{} |- (b8);
	           \path(b9) -- (b8);
	           \path(b0) --++ (-2,0)node [near start]{} |-(b8);
            \end{scope}
            \node (leyend) at (7.5,0){
            \begin{tabular}{>{\sffamily}l@{: }l}
            \multicolumn{1}{c}{\textbf{Note:}} \\
            $\rightarrow$ & 依赖于     \\
            Bad! & 不好的依赖关系\\
            \end{tabular}
            };
            \end{tikzpicture}
            \subsubsection{开放封闭原则OCP}
            概述:

            对扩展开放，对更改封闭。

            类模块应该是可扩展的，但是不可修改。

            （对稳定部分封闭，对变化部分开放。）
            \subsubsection{单一职责原则SRP}
            概述:

            一个类应该仅有一个引起它变化的原因。

            变化的方向隐含着类的责任。

            \subsubsection{替换原则LSP（继承关系）}
            概述：

            子类必须能够替换它们的积累（IS-A）。

            继承表达类型抽象。

            \subsubsection{接口隔离原则ISP}
            概述:

            不应该强迫客户程序依赖它们不用的方法。

            接口应该小而完备。

            \subsubsection{优先使用对象组合，而不是继承}
            概述：

            类继承通常为“白箱复用”，对象组合通常为“黑箱复用”

            继承在某种程度上破坏了封装性，子类父类耦合度高。

            而对象组合则只要求被组合的对象具有良好定义的接口，耦合度低。

            \subsubsection{封装变化点}
            概述：

            使用封装来创建对象之间的分解层，让设计者可以在分层在一侧进行修改，而不会对另一侧产生不良的影响，从而实现层次间的松耦合。

            \subsubsection{针对接口编程，而不是针对实现编程}
            概述：

            不将变量类型声明为某个特定的具体类，而是声明为某个接口。

            客户程序无需获知对象的具体类型，只需要知道对象所具有的接口。

            减少系统中各部分的依赖关系，从而实现“高内聚、松耦合”的类型设计方案。

            解释：

            面向接口设计意味着“接口标准化”，
            \subsubsection{设计经验}
            1.设计习语Design Idioms

            描述与特定编程语言相关的底层模式，技巧，惯用法。

            2.设计模式Design Patterns

            描述“类与相互通信的对象之间的组织关系，包括它们的角色、职责、协作方式等方面。解决变化中的复用性问题。

            3.架构模式Architectural Patterns

            描述系统中与基本结构组织关系密切的高层模式，包括子系统划分，职责，以及如何组织它们之间关系的规则。
        \subsection{重构关键技法}
            1.静态$\rightarrow$ 动态

            2.早绑定$\rightarrow$ 晚绑定

            3.继承$\rightarrow$组合

            4.编译时依赖$\rightarrow$运行时依赖

            5.紧耦合$\rightarrow$松耦合

        \subsection{组件协作}
            框架与应用，组件协作通过晚期绑定来实现框架与应用之间的松耦合。
            \subsubsection{Template Method}
            动机：有稳定的整体操作结果，但各个子步骤有很多改变的需求，或者由于固有原因（比如框架与应用之间的关系）而无法和任务的整体结构同时实现。

            如何在确定稳定操作结构的前提下，来灵活应对各个子步骤的变化或者晚期实现需求？

            模式定义：定义一个操作中的算法的骨架（实例中的run）（稳定），而将一些步骤延迟（变化）到子类中。Template Method 使得子类可以不改变（复用）一个算法的结构即可重定义（override重写）该算法的某些特定步骤。《设计模式》GoF

            选择该模式的前提：run（骨架）必须相对稳定（一年一变化比一月一变化要稳定）。

            极端：若一个程序中所有组件都不稳定都在变化，则不建议使用设计模式。使用设计模式的前提是至少有一个稳定点。若一个程序所有组件都稳定，则设计模式便毫无意义。

            设计模式的灵魂：在稳定与变化之间找隔离点，然后来分离它们从而来管理变化。将变化关到笼子里。

            其中的虚函数推荐用protected。

           \includegraphics[width=7cm, height=5cm]{template}
           
            \subsubsection{Strategy}
            动机：在软件构建过程中，某些对象使用的算法可能多种多样，经常改变，如果将这些算法都编码到对象中，将会使对象变得异常复杂；而且有时候支持不使用的算法也是一个性能负担（if else会增加代码段的开销）。

            如何在运行时根据需要透明地更改对象的算法？将算法与对象本身解耦，从而避免上述问题？

            模式定义：

            定义一系列算法，把他们一个个封装起来，并且使它们可互相替换（变化）。该模式使得算法可独立于使用它的客户程序（稳定）而变化（扩展，子类化）。《设计模式》GoF

            当有出现if else和switch可以考虑使用策略模式，if else和switch是传统的分而治之。决定稳定不变（如一星期7天）则可以使用if else。

            灵魂：用使用扩展的方式来应对以后业务的变化。
            
            \includegraphics[width=14cm, height=6cm]{strategy}
            
            \subsubsection{Observer/Event/观察窗口/向篮子里放鸡蛋}
            主要还是解决框架与应用的协作问题。

            动机：在软件构建过程中，我们需要为默写对象建立一种“通知依赖关系”--一个对象（目标对象）的状态发生改变，所有的依赖对象（观察者对象）都将得到通知。如果这样的依赖关系过于紧密，将使软件不能很好地抵御变化。

            使用面向对象技术，可以这种依赖关系弱化，并形成一种稳定的依赖关系。从而实现软件体系结构的松耦合。

            多继承：一个基类多个接口。

            模式定义：

            定义对象间的一种一对多（变化）的依赖关系，以便当一个对象（Subject）的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。《设计模式》

            java中的listen和中的事件都是使用了观察者模式。

            \includegraphics[width=14cm, height=8cm]{observer}
        \subsection{单一职责}
            \subsubsection{Decorator}
                设计模式的妙处：编译时让它们一样，让它们运行时不一样。编译时让它复用，它的变化、需求变化都放到运行时使用多态的方式让它支持变化。

                继承：编译时复用（提供接口），组合：运行时复用。

                原则：如果某一个类，它有多个子类都有同样的字段，应该把这个往上提。

                动机：在某些情况下我们可能会“过度地使用继承来扩展对象的功能”。由于继承为类型引入的静态特质，使得这种扩展方式缺乏灵活性；并且随着子类的增多（扩展功能的增多），各种子类的组合（扩展功能的组合）会导致更多子类的膨胀。

                如何使“对象功能的扩展”能够根据需要来动态地实现？同时避免“扩展功能的增多”带来的子类膨胀问题？从而使得任何“功能扩展变化”所导致的影响降为最低？

				\includegraphics[width=9cm, height=7cm]{decorator}
            \subsubsection{Bridge}
                动机：由于某些类型的固有的实现逻辑，使得它们具有两个变化的维度，乃至多个维度的变化。

                如何应对这种“多维度的变化”？如何利用面向对象技术来使得类型可以轻松地沿着两个乃至多个方向变化，而不引入额外的复杂度？

                模式定义：将抽象部分（业务功能）与实现部分（平台实现）分离，使它们都可以独立地变化。

                \includegraphics[width=14cm, height=6cm]{bridge}
                
        \subsection{从范围划分}
            \subsubsection{类模式处理类与子类的静态关系（偏继承）}

            \subsubsection{对象模式处理对象间的动态关系（偏组合）}

        \subsection{C++语言知识点}
            Algorithms + Data Structures = Programs。
            \subsubsection{1、类中使用虚的析构函}
                \begin{lstlisting}[language=C++]
                class Example{
                public:
                    virtual ~Example(){}
                };
                \end{lstlisting}
            \subsubsection{2、指针和多态}

    \section{STL学习笔记}
        \subsection{六大部件}
            1.容器(Containers):解决了存储结构的问题。

            2.分配器(Allocators):支持容器分配存储单元的数目。

            3.算法(Algorithms):功能模板函数操作。

            4.迭代器(Iterators):泛化指针，为了访问和存储内存。

            5.适配器(Adapters):转换器（容器，迭代器，房函数）比如有否定适配器和绑定适配器。

            6.仿函数(Functors):function object。

        \subsection{容器的选择问题}
                \subsubsection{1. 复杂度Big-oh}

                   O(1)or O(c)：常数时间（constant time）。

                   O(n)：线性时间（linear time）。

                \subsubsection{2.数据的分布、特性}

                    a. 会经常在中间安插一个数据吗？

                    b. 会经常从尾巴放数据还是常常从头部放数据？

                    c. 会经常查找一个数据吗？

        \subsection{STL容器range特点}
            容器采用“前闭后开”区间，*.end()指向最后一个元素的下一个。
        \subsection{C++11 特性}
            \subsubsection{1.C++11 range-based for statement}
                \begin{lstlisting}[language=C++]
                    for(decl : coll){
                    statement
                    }
                    for(int i:{2,3,5,7,8,133}){
                        std::cout<<i<<std::endl;
                    }
                \end{lstlisting}
            \subsubsection{2.C++11 auto的使用}
                \begin{lstlisting}[language=C++]
                    list<string> c;
                    ...
                    list<string>::iterator ite;
                    ite = ::find(c.begin(),c.end(),target);

                    list<string> c;
                    ...
                    auto ite= ::find(c.begin(),c.end(),target);
                \end{lstlisting}
        \subsection{容器-结构与分类}
            \subsubsection{1.sequence Containers（按放入次序排列）}

                Array(fixed number of elements),vector（尾部可扩展的内存，内存是两倍增加的并会另选一块内存，只允许尾部可放入）,

                Deque （首front 尾back 首尾可扩展的内存，分段（buffer）连续（map），无内部sort，stack和queue的基础结构）,

                List （双向环状链表）,

                （C++11）Forward-List （单向链表，只允许头部可放入，尾部不是不可以只是效率太低），

                (GNU C++)slist （同Forward-List 一样，在头文件ext\\slist中）。

            \subsubsection{2.Associative Containers:(元素有key和value，适合大量快速查找，标准库内部基础为红黑树：高度平衡树)}

                Set（key和value为同一部分，key唯一）Multiset （插入为insert）,

                Map（每个节点有key 和value 两个不同部分,需要pair打包pair<keytype,valtype>(key,value)也可以c[key]=value,解包时
                \\* 用*.first 和*.second）Multimap（multi 表示key可以重复,只能用pair打包因为key可以重复）。

            \subsubsection{3.Unordered Containers:（不定序,HashTable Separate Chaining，有bucket和forward-List组成）}

                Unordered Set/Multimap,Unordered Map/Multimap。



                经验法则: 如果元素的个数大于或等于bucket的数目，需要加大bucket的个数并且重新打撒元素放入。
        \subsection{gnu c++ 4.9.2}
            \subsubsection{Generic Programming}
                特点：将datas和methods分开来，也就是说将算法和容器分开来，而两者通过迭代器来联系。而（Object-Oriented programming）是将datas和methods 结合起来。

                GP的好处：Containers和Algorithms团队可各自闭门造车，期间以Iterator 连通即可。Algorithms通过Iterators确定操作范围，并通过Iterators取用Container 元素。
            \subsubsection{algorithms的基础}
                所有algorithms，期内最终涉及元素本身的操作，无非就是比大小。
            \subsubsection{list不能用全局sort}

            \subsubsection{操作符重载Overloaded operators}
            网站http://en.cppreference.com/w/cpp/operators

            \subsubsection{模板（泛化）}
            一、类模板形如：
            \begin{lstlisting}[language=C++]
            template <typename T>//T未定
            class complex
            {
            public:
                complex (T r=0,T i=0)
                :re(r),im(i)
                { }
                complex& operator += (const complex&);
                T real () const {return re;}
                T imag () const {return im;}
            private:
                T re,im;
                friend complex$ __doapl (complex*,const complex&);
            };

            {
                complex<double> c1(2.5,6);
                complex<int> c2(5,6);
                ...
            }
            \end{lstlisting}

            二、函数模板（function templates）
            \begin{lstlisting}[language=C++]
            template <class T>//class 和 typename 相同只不过class更老点.
            inline
            const T& min(const T& a,const T& b)
            {
                return b<a ? b:a;  //其中的'<'来自数据b和a的<操作符重载.
            }
            class stone
            {
            public:
                stone(int w,int h,int we)
                :_w(w),_h(h),_weight(we)
                { }
                bool operator<(const stone& rhs)const
                {return _weight < rhs.weight;}
            private:
                int _w,_h,_weight;
            };

            stone r1(2,3),r2(3,3),r3;
            r3 = min(r1,r2);

            \end{lstlisting}
            member template成员模板

            常在构造函数这点使用成员模板。这样可以做到使用pair对直接初始化。
            \begin{lstlisting}[language=C++]
            template <class T1,class T2>
            struct pair
            {
                T1 first;
                T2 second;
                ...

                template <class U1,class U2>
                pair(const pair<U1,U2>&p)
                :first(p.first),second(p.second){ }
            }
            pair<Base1,Base2>p2(pair<Derived1,Derived2>());
            //将一个由鲫鱼和麻雀构成的pair放进（拷贝到）一个由鱼类和鸟类构成的pair中。
            \end{lstlisting}
            例如：
            \begin{lstlisting}[language=C++]
            template<typename _Tp>
            class shared_ptr:public __shared_ptr<_Tp>
            {
                ...
                template<typename _Tp1>
                explicit shared_ptr(_Tp1* __p)
                :__shared_ptr<_Tp>(__p){}
                ...
            }
            //一般指针的up-cast
            Base1 * ptr = new Drived1; //up-cast base1为鸟类,Drived1为麻雀
            //智能指针的Up-cast
            shared_ptr<Base1>sptr(new Derived1);


            \end{lstlisting}
            Specialization，全特化（专属）
            比如
            \begin{lstlisting}[language=C++]
            template <class type>
            struct  __type_traits{
                typedef __true_type this_dummy_member_must_be_first;
                typedef __false_type has_trivial_default_constructor;
            };
            //特化如下
            template<> struct __type_traits<int>{
                typedef __true_type has_trivial_default_constructor;
            };
            \end{lstlisting}
            specialization全特化
            \begin{lstlisting}[language=C++]
            template <class Key>
            struct hash{ };

            template<>
            struct hash<char>
            {
                size_t operator()(charx)const
                {
                    return x;
                }
            };
            \end{lstlisting}
            Partial Specialization,偏（局部）特化
            \begin{lstlisting}[language=C++]

            //偏特化（个数上的局部）
            template<class Alloc>
            class vector<bool, Alloc>
            {
                ...
            };
            \end{lstlisting}

            \begin{lstlisting}[language=C++]
            //偏特化（范围上的局部）
            template<class T,class Alloc=alloc>
            class vector<T*>//此处将任意类型T局部为指针类型的，缩小其范围。
            {
                ...
            };
            \end{lstlisting}
            三、Member Templates,成员模板
        \subsection{通用库算法}
            \subsubsection{1. std::find 为循序查找}

            \subsubsection{2. std::bsearch 为二分查找}
        \subsection{容器内部算法}
            \subsubsection{1. c.sort 一般标准库中也有::sort,但当容器自己有sort时应优先使用自己的sort}
        \subsection{分配器}
            直接用不好用，因为它在释放内存时需要指明字节数。
            allocator$\rightarrow$ allocator.allocate$\rightarrow$operator new
            $\rightarrow$malloc。
            \subsubsection{分配器}
            推荐使用G2.9分配器alloc或G4.9$_pool_alloc$。

            gnu c++文件:$<atl_alloc.h>$。

            其它版本的allocator没有特殊的设计。

            每个malloc分配的内存都有额外的开销来记录所有分配内存的信息cookie。而因为每个容器中元素的内存大小一样，所以gnu c++对其的优化是一个容器中所有元素使用一个cookie来说明信息。

            用例：

            \begin{lstlisting}[language=C++]
                vector<string,__gnu_cxx::__pool_alloc<string>>vec;
            \end{lstlisting}

        \subsection{容器}
            \subsubsection{list}
                1.聪明的迭代器iterator在class list中有
                \begin{lstlisting}[language=C++]
                class list{
                    ...
                public:
                    typedef __list_iterator<T,T&,T*> iterator;
                    ...
                }
                \end{lstlisting}
                \begin{lstlisting}[language=C++]
                //其中__list_iterator为
                template<class T,class Ref,class Ptr>
                struct __list_iterator{
                    typedef T value_type;
                    typedef Ptr pointer;
                    typedef Ref reference;
                ...
                \end{lstlisting}
                聪明的迭代器的使用实例：
                \begin{lstlisting}[language=C++]
                list<Foo>::iterator ite;
                ...
                *ite;//获得 a Foo object
                ite->method();
                //唤起 Foo::method()
                //相当于(*ite).method();
                //相当于(&(*ite))->method();
                ite->field = 7;
                //赋值Foo object's field
                //only if field is public
                //相当于(*ite).field = 7;
                //相当于(&(*ite))->field = 7;
                \end{lstlisting}
                2.节点设计代码
                \begin{lstlisting}[language=C++]
                template <class T>
                struct __list_node {
                typedef void* void_pointer;
                void_pointer prev;
                void_pointer next;
                T data;
                };
                \end{lstlisting}
                3.涉及的$list_iterator $操作符重构
                \begin{lstlisting}[language=C++]
                \\prefix form
                self & operator++()//有&可以连续两次使用前++
                {
                    node = (link_type)((*node).next);
                    return *this;
                }
                \\postfix form
                self operator++(int)//无&的原因是为了模拟整数无法连续两次后++
                \\形如int i(6);i++++;（栈区变量）
                {
                    self tmp = *this;//不会唤起operator*因为*this已被解释为=copy的参数。=会唤起copy
                    ++*this;
                    return tmp;
                }
                \end{lstlisting}
                \begin{lstlisting}[language=C++]
                reference operator*() const//reference为T&
                {
                    return (*node).data;
                }
                pointer operator->()const
                {
                    return &(operator*());
                }
                \end{lstlisting}
        \subsection{代码测试经验}
            \subsubsection{1. 写测试程序时常将为了让每个程序尽量独立又可以放在一起，此时比较好的方法是可以将每个测试程序单元单独做一个命名空间}
                \begin{lstlisting}[language=C++]
                      namespace example
                    {
                        test_function;
                    }
                \end{lstlisting}

            \subsubsection{2. 变量的声明和定义在正规程序一般一块放到包体里开始，写测试程序比较好的习惯是用到变量散开来并且用到时再声明的方法，同时为了变量好找一点，可以取消变量声明代码的缩进}
                \begin{lstlisting}[language=C++]
                    void test()
                    {
                        ...
                    long index=0;
                        ...
                    }
                \end{lstlisting}


\end{document}
